package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LC_637_AverageofLevelsinBinaryTree {

    public static void main(String[] args) {

    }

    public class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Integer> count = new ArrayList<>();
            List<Double> res = new ArrayList<>();
            average(root, 0, res, count);
            for (int i = 0; i < res.size(); i++)
                res.set(i, res.get(i) / count.get(i));
            return res;
        }

        void average(TreeNode t, int i, List<Double> sum, List<Integer> count) {
            if (t == null)
                return;
            if (i < sum.size()) {
                sum.set(i, sum.get(i) + t.val);
                count.set(i, count.get(i) + 1);
            } else {
                sum.add(1.0 * t.val);
                count.add(1);
            }
            average(t.left, i + 1, sum, count);
            average(t.right, i + 1, sum, count);
        }
    }

    public class Solution_2 {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> result = new ArrayList<>();
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            while (!q.isEmpty()) {
                int n = q.size();
                double sum = 0.0;
                for (int i = 0; i < n; i++) {
                    TreeNode x = q.poll();
                    sum += x.val;
                    if (x.left != null) q.add(x.left);
                    if (x.right != null) q.add(x.right);
                }
                result.add(sum / n);
            }
            return result;
        }
    }
}